{
  // 1.用简洁的代码实现indexOf()
  const indexOf = (arr,target,start = 0) =>{
    if(start<0) start = 0;
    if(start>arr.length-1) return -1;
    for(let i = start;i<arr.length;++i){
      if(arr[i] === target) return i
    }
    return -1;
  }
  let x = indexOf('abcdef','b')
  console.log(x)
}
{
  // 2.filter数组去重
  let arr1 = [1,2,3,4,4,5,5,6,7,11,11,12,13,14,15,16,16];
  let arr2 = arr1.filter((item,index,self)=>self.indexOf(item) === index);
  console.log(arr2);
}
{
  // 判断数组arr1是否全是偶数
  // 判断数组arr2是否至少有一个偶数

  const arr1=[1, 2, 3, 4, 5];
  const arr2=[1, 4, 6, 8, 10];
  console.log(
      arr1.every(function(value, index, array){
        return value % 2 == 0;
      })
  );    // false
  console.log(
      arr2.some(function(value, index, array){
        return value % 2 == 0;
      })
  );    // true
}
{
  // reduce使用
  let arr1 = [1,2,3,4,5,6,7,8,9,10];
  let sum = arr1.reduce((pre,cur)=>{
    return pre+cur
  },100);
  console.log(sum);
  let aString = 'aabbccdeeefff';
  let count = aString.split('').reduce((pre,cur)=>{
    pre[cur] ? pre[cur]++ : pre[cur] =1;
    return pre
    },{})
  console.log(count)
}
{
  //includes
  const arr = [7,1,2,3,4,5,6,7];
  console.log(
      arr.includes(5)
  ) // true
  console.log(
      arr.indexOf(5)
  ) // 4
  console.log(
      arr.lastIndexOf(7,-1)
  ) // 7
  console.log(
      arr.lastIndexOf(7,-2)
  ) // 0
}
{
  // 两数之和
  const twoSum = (nums, target) => {
    let mapObj = {};
    let res = [];
    nums.forEach((e, i) => mapObj[e] = i);
    for(let i=0;i<nums.length;i++) {
      let j = mapObj[target - nums[i]];
      if(j && j !== i) {
        res = [i, j];
        break;
      }
    }

    return res;
  };
  let nums = [2,7,11,15];
  let target = 13;
  console.log(twoSum(nums,target))
}
{// 两数之和
  const twoSum = (nums, target) => {
    let map = new Map();
    let res = [];
    nums.forEach((e, i) => map.set(e, i));
    console.log(map)

    for(let i=0;i<nums.length;i++) {
      let j = map.get(target - nums[i]);
      if(j && j !== i) {
        res = [i, j];
        break;
      }
    }

    return res;
  };
  let nums = [2,7,11,15];
  let target = 13;
  console.log(twoSum(nums,target))
}
{
  /*
  给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
  对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
  你可以返回任何满足上述条件的数组作为答案。
   */
  const sortArrayByParityII = function(A) {
    let result = [];
    let jArr = A.filter((item)=>item % 2 == 1);
    let oArr = A.filter((item)=>item % 2 == 0);
    for(let i=0;i<jArr.length;i++){
      result.push(oArr[i]);
      result.push(jArr[i]);
    }
    return result;
  };
  let s = [4,2,5,7];
  console.log(sortArrayByParityII(s))
}
{
  let nums = [1,2,1,2,1];
  let k = 3;
  const subarraySum = function(nums, k) {
    let count = 0;
    for(let i=0;i<nums.length;i++){
      let sum = 0;
      for(let j=i;j<nums.length;j++){
        sum += nums[j];
        if(sum === k){
          count++;
          break;
        }
      }
    }
    return count
  };
  console.log(subarraySum(nums,k))
}
{
  // 整数反转
  const reverse = function(x) {
    let numList = x.toString().split('');
    let reverseNum;
    const maxVal = Math.pow(2,31) - 1;
    const minVal = Math.pow(-2,31);
    if(numList[0] === '-'){
      numList.shift();
      reverseNum = -parseInt(numList.reverse().join(''));
    }else{
      reverseNum = parseInt(numList.reverse().join(''));
    }
    console.log(reverseNum>maxVal)
    if(reverseNum>maxVal || reverseNum<minVal){
      reverseNum = 0;
    }
    return reverseNum
  };
  console.log(reverse(123))
}
{
  // 整数回文数
  const isPalindrome = function(x) {
    if(x<0) return false;
    let now = 0;
    let old = x;
    while(old>0){
      now = now*10 + old%10;
      old = Math.floor(old/10);
    }
    if((x-now === 0)) return true;
    else return false;
  };
  console.log(isPalindrome(10))
}
{
  //罗马数字转整数
  const romaToInt = function (s) {
    //左减右加（看题解） 执行用时160ms超过80.12%  内存消耗39.8MB超过100.00%
    // let map = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000},
    //     sum = 0, loop = 0, num = 0, now = 0;
    // while(loop < s.length) {
    //     now = map[s[loop]];
    //     if(num < now) {
    //         sum -= num;
    //     } else {
    //         sum += num;
    //     }
    //     num = now;
    //     loop++;
    // }
    // sum += num;
    // return sum;
    let romaList = {
      M:1000, CM:900, D:500,CD:400, C:100,XC:90, L:50, XL:40, X:10, IX:9, V:5, IV:4, I:1
    };
    let result = 0;
    while (s.length){
      let flag = romaList[(s[0]+s[1])];
      if(flag){
        s = s.substring(2)
      }else {
        flag = romaList[s[0]];
        s = s.substring(1);
      }
      result += flag;
    }
    return result
  };
  // romaToInt('MCMXCIV');
}
{
  // 罗马数转整数
  const romaToInt = function (s) {
    let romaString = ['M','CM','D','CD','C','XC','L','XL','X','IX','V','IV','I'];
    let romaNum = [1000,900,500,400,100,90,50,40,10,9,5,4,1];
    let result = 0;
    while (s.length){
      let flag = romaString.indexOf((s[0]+s[1]));
      if(flag>=0){
        s = s.substring(2)
      }else {
        flag = romaString.indexOf(s[0]);
        s = s.substring(1);
      }
      console.log(flag)
    }
    return result
  };
  // console.log(romaToInt('III'))
}
{
  // 罗马数字转整数
  const romaToInt = function (s) {
    let romaList = {
      M:1000, D:500,C:100,L:50, X:10,V:5, I:1
    };
    let result = 0;
    for(let i=0;i<s.length;i++){
      let left = romaList[s[i]];
      let right = romaList[s[i+1]];
      left<right ? result -= left : result+=left;
    }
    return result;
  }
  console.log(romaToInt('CCC'))
}
{
  // 整数转罗马数
  const intToRoman = function(num) {
    // let romaString = ['I','IV','V','IX','X','XL','L','XC','C','CD','D','CM','M'];
    let romaString = ['M','CM','D','CD','C','XC','L','XL','X','IX','V','IV','I'];
    let romaNum = [1000,900,500,400,100,90,50,40,10,9,5,4,1];
    let loop = 0;
    let result = '';
    while (loop<romaNum.length){
      while(num>=romaNum[loop]){
        num -= romaNum[loop];
        result += romaString[loop]
      }
      loop++;
    }
    return result

  };
  intToRoman(123)
}
{
  var intToRoman = function(num) {
    var hashMap = {
      1000: 'M',
      900: 'CM',
      500: 'D',
      400: 'CD',
      100: 'C',
      90: 'XC',
      50: 'L',
      40: 'XL',
      10: 'X',
      9: 'IX',
      5: 'V',
      4: 'IV',
      1: 'I'
    };
    var s = '';
    for(let key of Object.keys(hashMap).reverse()) {

      if(num >= key) {
        var count = parseInt(num / key);
        console.log(hashMap[key].repeat(count))
        s += hashMap[key].repeat(count);
        // s = s.repeat(count-1)
        // for(var i = 0; i < count; i++) {
        //   s = s.concat(hashMap[key]);
        // }
        num -= key * count;
      }
    }
    return s;
  };
  // console.log(intToRoman(23))
}



{
  //快乐数
  const isHappy = n => {
    let set = new Set(),
        sum = 0;
        n+='';
    while (sum != 1) {
      sum = 0;
      for (let i in n) {
        sum += n[i] * n[i];
      }
      n = sum+'';
      if (set.has(sum)) return false;
      set.add(sum);
    }
    return true;
  }
  // console.log(isHappy(123))
}
{
  const isHappy = function (n) {
    let arr = [];
    let sum = 0;
    n = n+'';
    while (sum != 1){
      sum = 0;
     for( let i of n ){
       sum += Math.pow(i,2);
     }
     n = sum +'';
     if(arr.indexOf(sum)>-1) return false;
     arr.push(sum);
    }
    return true;
  }
  // console.log(isHappy(132))
}
{
  // 无重复最长字符串
  const lengthOfLongestSubstring = function(s) {
    let length = s.length;
    let arr = [],max = 0;
    for(let i=0;i<length;i++){
      let index = arr.indexOf(s[i]);
      if(index !== -1){
        arr.splice(0,index+1);
      }
      arr.push(s[i]);
      console.log(arr,i)
      max = Math.max(arr.length,max);
    }
    return max
  };
  console.log(lengthOfLongestSubstring("pwpkew"))
}
{
  function quickSort(arr) {
    if (arr.length <= 1) {
      return arr;//如果数组只有一个数，就直接返回；
    }
    var num = Math.floor(arr.length / 2);//找到中间数的索引值，如果是浮点数，则向下取整
    var numValue = arr.splice(num, 1);//找到中间数的值
    var left = [];
    var right = [];
    for (var i = 0; i < arr.length; i++) {
      if (arr[i] < numValue) {
        left.push(arr[i]);//基准点的左边的数传到左边数组
      } else {
        right.push(arr[i]);//基准点的右边的数传到右边数组
      }
    }
    return quickSort(left).concat(numValue, quickSort(right));//递归不断重复比较
  }
  console.log(quickSort([32,45,37,16,2,87]));

  function quickSort2(arr,low = 0,high = arr.length-1) {
    if(arr.length <= 1){
      return arr;//如果数组只有一个数，就直接返回；
    }
    let left = low;
    let right = high;
    let basic = arr[low];
    while (left<right){
      while (left<right && arr[right]>basic){
        right--
      }
      while (left<right && arr[left]<=basic){
        left++
      }
      if(left<right){
        const temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp
      } else{
        const temp = arr[low];
        arr[low] = arr[left];
        arr[left] = temp;
        quickSort2(arr, low, left - 1)
        quickSort2(arr, right + 1, high)
      }
    }
    return arr;
  }
  console.log(quickSort2([32,45,37,16,2,87]));
}
{
  var mincostTickets = function (days, costs) {
    let max = days[days.length - 1];
    let dp = new Array(max + 1).fill(Infinity);
    let cost1, cost7, cost30;
    dp[0] = 0;
    for (let i = 1; i <= max; i++) {
      if (days.indexOf(i) !== -1) {
        if (i === days[0]) {
          dp[i] = Math.min(...costs);
        } else {
          cost1 = dp[i - 1] + costs[0];
          cost7 = i >= 7 ? dp[i - 7] + costs[1] : costs[1];
          cost30 = i >= 30 ? dp[i - 30] + costs[2] : costs[2];
          dp[i] = Math.min(cost1, cost7, cost30);
        }
      } else {
        dp[i] = dp[i - 1];
      }
    }
    console.log(dp)
    return dp[max]
  };
  let days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15];
  console.log(mincostTickets(days,costs))
}